#include <string.h>
#include <iostream>
using namespace std;

/*
  链表 
*/
void my_list();
struct node *add_to_list(struct node *list,int n); //新增结点
void print_list(struct node *list);//遍历链表
struct node *search_list(struct node *list,int n); //查找链表结点
struct node *search_list01(struct node *list,int n);
struct node *search_list02(struct node *list,int n);

struct node *delete_list_node(struct node *list,int n);//删除结点

int main(){
  my_list();
  return 0;
}
//结点结构
struct node{
  int value; 
  struct node *next; //指向下一个结点的指针
};

void my_list(){

  //需要有一个始终指向表中第一个结点的变量。
  struct node *first = NULL;

  struct node *new_node;
  new_node = (node*)malloc(sizeof(node)); //现在new_node指向了一个内存块，且此内存块正好能放下一个node结构

  //将把数据存储到新结点的成员value中
  (*new_node).value = 20;
  //采用间接寻址运算符*（引用new_node指向的结构）​，然后用选择运算符.（选择此结构内的一个成员）​。
  //在*new_node两边的圆括号是强制要求的，因为运算符.的优先级高于运算符*

  //右箭头选择（right arrow selection）  ->
  //利用指针访问结构中的成员是很普遍的，因此C语言针对此目的专门提供了一种运算符。此运算符称为右箭头选择（right arrow selection）​，它由一个减号跟着一个->组成。
  
  //运算符->是运算符*和运算符.的组合，它先对new_node间接寻址以定位所指向的结构，然后再选择结构的成员value。
  new_node->value = 30;

  //把结点插入链表
  //1. 修改结点的成员next，使其指向先前在链表开始处的结点：
  new_node->next = first; //把first的值(地址),给node的next,执向null 注:不是指向first的指针,first变化不会影响这个值
  
  //2. 使first指向新结点
  first = new_node; //修改first的值(new_node的地址)

  cout << "001 == 01结点 - 第一个结点的值: " << first->value << endl;
  cout << "001 == 01结点 - 第一个结点的地址: " << first->next << endl; //first变化不会影响这个值
  cout << ""<< endl;

  //添加结点
  first = add_to_list(first,40);
  first = add_to_list(first,100);
  first = add_to_list(first,50);
  first = add_to_list(first,110);
  first = add_to_list(first,60);

  //遍历链表
  print_list(first);
  
  //查找结点
  struct node *find_node = search_list02(first,120);

  if(find_node != NULL){
    cout << "003 == search_list - 查询结点结果: " << find_node->value << endl;  
  }else{
    cout << "003 == search_list - 未查询到结果" << endl; 
  }
  cout << ""<< endl;
  
  first = delete_list_node(first,60);
  print_list(first);

}

//新增结点到链表中 (当调用add_to_list函数时，需要把它的返回值存储到first中)
//list（指向旧链表中首结点的指针）和n（需要存储在新结点中的整数）​。
struct node *add_to_list(struct node *list,int n){
  struct node *new_node;
  //创建结点
  new_node = (node*)malloc(sizeof(struct node)); 

  if(new_node == NULL){
    cout << "err06 没有内存可以分配"<< endl;
    exit(EXIT_FAILURE);
  }

  new_node->value = n;
  new_node->next = list;

  //add_to_list函数不会修改指针list，而是返回指向新产生的结点的指针（现在位于链表的开始处）​。
  return new_node;
}
/*
  用add_to_list函数直接更新first，而不是为first返回新的值，这样做是个技巧。
  
  假设修改了函数使它不再返回new_node，而是把new_node赋值给list。
  void add_to_list(struct node *list,int n){
    ....
    list = new_node;
  }

  假设按照下列方式调用函数add_to_list
  add_to_list(first,40);

  在调用点，会把first复制给list。​（像所有其他参数一样，指针也是按值传递的。​）函数内的最后一行改变了list的值，使它指向了新的结点。
  但是，此赋值操作对first没有影响。

  让函数add_to_list修改first是可能的，但是这就要求给函数add_to_list传递一个指向first的指针。

  指向指针的指针。
*/




//遍历链表
void print_list(struct node *list){
  struct node *p;
  cout << "002 结点的值: ";

  //赋值表达式p = p->next使指针p从一个结点移动到下一个结点
  for (p = list; p != NULL; p = p->next)
  {
    cout<< p->value << " ";
  }
  cout << endl;
}

//查找链表结点
struct node *search_list(struct node *list,int n){
  struct node *p;

  for (p = list; p != NULL; p = p->next)
  {
    if(p->value == n){
      return p;
    }
  }

  return NULL;  
}

//查找链表结点 - 优化查询01
struct node *search_list01(struct node *list,int n){

  //因为list是原始链表指针的副本，所以在函数内改变它不会有任何损害。
  for (;list != NULL; list = list->next)
  {
    if(list->value == n){
      return list;
    }
  }

  return NULL;  
}

//查找链表结点 - 优化查询02
struct node *search_list02(struct node *list,int n){

  //把判定list->value == n和判定list != NULL合并起来：
  while(list != NULL && list->value != n)
  {
    list = list->next;
  }

  //因为到达链表末尾处时list为NULL，所以即使找不到n，返回list也是正确的。
  return list;  
}


//删除结点
struct node *delete_list_node(struct node *list,int n){
  //删除结点 - 3个步骤
  //(1) 定位要删除的结点 
  //如果按照显而易见的方式搜索链表，那么将在指针指向要删除的结点时终止搜索。但是，这样做就不能执行第2步了，因为第2步要求改变前一个结点。
  struct node *del_node = search_list(list,n);

  //这里将使用“追踪指针”的方法：在第1步搜索链表时，将保留一个指向前一个结点的指针（prev）​，还有指向当前结点的指针（cur）​。如
  struct node *curr_node = list;
  struct node *prev_node = NULL;
  for (; curr_node != NULL && curr_node->value != n; )
  {
    prev_node = curr_node;
    curr_node =curr_node->next;
  }

  // if(prev_node != NULL){
  //   cout << "004 == del_list() 查找要删除的结点的上一个结点 " << prev_node->value << endl;  
  // }else{
  //   cout << "004 == 未查询到结果" << endl; 
  // }  

  //(2) 改变前一个结点，从而使它“绕过”删除结点
  if(curr_node == NULL){
    return list;
  }else if(prev_node == NULL){
    list = list->next;
  }else{
    prev_node->next = curr_node->next;
  }
  
  //(3) 调用free函数收回删除结点占用的内存空间。
  free(curr_node);
  
  return list;
}







